1. Field of the Invention
The present disclosure relates generally to automatic memory management and more specifically to a generational garbage collection technique that optimizes the locality of objects in memory.
2. Description of the Related Art
Improving memory data locality in systems contributes to optimized performance of applications. The performance of an application being executed is enhanced when data or objects being used by the application may be easily accessed by the system. It is optimum for objects or data that may be accessed frequently or close in time to be located within the same memory space, such as the same cache line or cache page.
There are many different types of garbage collection algorithms, but only the garbage collection algorithm that copy or move objects may be helpful improving the locality of objects in a memory. For example, a copying garbage collector moves objects from one area or space in memory to another. A copying garbage collector may improve locality by searching for data, collecting all the live objects in one area or heap of memory, and copying the live objects to another area of memory to compact the location of live objects into one space.
Hierarchical copying garbage collection improves locality by co-locating objects that are hierarchically related. Hierarchically related objects are those that are directly or indirectly connected to each other via references between them. For instance, parents, children, siblings, cousins, grandparents and grandchildren are all hierarchically related. It relies on empirical evidence that objects that are used close in time are often hierarchically related to one another. Parallel hierarchical copying garbage collection further improves locality by allowing multi-threaded compaction operations within a memory. Further details that illustrate how parallel hierarchical copying garbage collection improve locality and improve system performance are disclosed in U.S. patent application Ser. No. 11/450,946 to Siegwart et al., entitled “Locality With Parallel Hierarchical Copying Garbage Collection,” filed Jun. 9, 2006 and incorporated herein for all purposes. In the Siegwart et al. patent application, the parallel hierarchical copying garbage collection algorithm is generational. However, even in parallel hierarchical copying algorithms, there may be cases that compromise or defeat optimum locality where children of an object are copied outside the space or locality of the object.
In one example, during a copying garbage collection, a live object in the allocation space of a heap may be referenced. The object may be scavenged or copied from the allocation space of the heap to the survivor space. In the survivor space, the slots of the copied parent object may be scanned and the possibility exists that the children referenced in each of the slots of the parent object may be not be copied into the same space as the parent object. Rather, the children may be separated into a space of memory based on their generation or age.
For example, if a child is considered young, it may be copied into the survivor space along with the parent object. If a child of the object is old, it may be separated from the parent object and copied into the tenure region of memory, because of its age. The tenure region may be orders of magnitude of the cache line size or page size away from the survivor region. Therefore, good locality of the old child to the parent object may be defeated. A child of a different generation from its parent object may not achieve good locality with the parent object because it may be separated from the parent object into a different space.